<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
  <head>
    <meta charset="utf-8" />
    <meta name="generator" content="pandoc" />
    <meta
      name="viewport"
      content="width=device-width, initial-scale=1.0, user-scalable=yes"
    />
    <title>README</title>
    <style type="text/css">
      code {
        white-space: pre-wrap;
      }
      span.smallcaps {
        font-variant: small-caps;
      }
      span.underline {
        text-decoration: underline;
      }
      div.column {
        display: inline-block;
        vertical-align: top;
        width: 50%;
      }
    </style>
  </head>
  <body>
    <h1 id="analysis-of-algorithms">Analysis of Algorithms</h1>
    <p>
      Analysis of the running time of various code snippets with respect to the
      input size of <code>n</code>.
    </p>
    <hr />
    <h2 id="a.">a.</h2>
    <pre><code>a = 0
while a &lt; n * n * n:
  a = a + n * n</code></pre>
    <h3 id="linear-time-on">Linear time — O(n)</h3>
    <p>
      It takes <code>n</code> iterations for <code>a += n²</code> to reach
      <code>n³</code>
    </p>
    <h5 id="example">Example:</h5>
    <p>If given <code>n = 5</code>, then <code>n³ = 125</code>.</p>
    <p>
      Each iteration of the while loop is adding <code>n * n</code> to
      <code>a</code>.
    </p>
    <pre><code>25
50
75
100
125</code></pre>
    <p>
      Another way to think about this: How many times do we we add
      <code>n * n</code> to get <code>n * n * n</code>?
    </p>
    <p>
      If <code>n = 5</code>:
      <code>(5 * 5) + (5 * 5) + (5 * 5) + (5 * 5) + (5 * 5)</code>
    </p>
    <hr />
    <h2 id="b.">b.</h2>
    <pre><code># array is of length n
i = len(array) - 1

while array[i] &gt; x and i &gt;= 0:
  i = i // 2</code></pre>
    <h3 id="logarithmic-time-olog-n">Logarithmic time — O(log n)</h3>
    <p>The value of <code>i</code> is halved on each iteration of the loop.</p>
    <hr />
    <h2 id="c.">c.</h2>
    <pre><code>sum = 0;
for (i = 0; i &lt; sqrt(n) / 2; i++)
  for (j = i; j &lt; 8 + i; j++) for (k = j; k &lt; 8 + j; k++) sum++;</code></pre>
    <h3 id="square-root-on-osqrtn">
      Square root — <code>O(√n)</code> / <code>O(sqrt(n))</code>
    </h3>
    <p>
      The outer for loop grows with the size of <code>√n</code>. The
      <code>√n / 2</code> is a constant operation, as are the two inner for
      loops, so they’re not considered.
    </p>
    <hr />
    <h2 id="d.">d.</h2>
    <pre><code>sum = 0;
for (i = 1; i &lt; n; i *= 2) for (j = 0; j &lt; n; j++) sum++;</code></pre>
    <h3 id="linearithmic-on-log-n">Linearithmic — O(n log n)</h3>
    <p>
      Both for loops will grow as <code>n</code> grows, but the inner for loop
      is linear, and the outer for loop is logarithmic since
      <code>i</code> doubles with each iteration.
    </p>
    <hr />
    <h2 id="e.">e.</h2>
    <pre><code>sum = 0;
for (i = 0; i &lt; n; i++)
  for (j = i + 1; j &lt; n; j++)
    for (k = j + 1; k &lt; n; k++) for (l = k + 1; l &lt; 10 + k; l++) sum++;</code></pre>
    <h3 id="cubic-on³">Cubic — O(n³)</h3>
    <p>
      The inner-most for loop is considered constant (it only
      <em>ever</em> iterates up to 10 and doesn’t grow with input size
      <code>n</code>), whereas the other 3 for loops are linear and grows with
      <code>n</code>.
    </p>
    <hr />
    <h2 id="f.">f.</h2>
    <pre><code>// bunnies === n
const bunnyEars = (bunnies) =&gt; {
  if (bunnies === 0) return 0;
  return 2 + bunnyEars(bunnies - 1);
};</code></pre>
    <h3 id="linear-on">Linear — O(n)</h3>
    <p>
      Each recursive call
      <code>returns 2 + previous recursive call's return value</code> with the
      exception of the base case <code>if</code> statement where 0 is returned.
    </p>
    <p>
      What makes this linear is the value of <code>bunnies</code> or
      <code>n</code> is decremented by 1 with each recursive call until
      <code>n === 0</code>.
    </p>
    <h5 id="example-1">Example:</h5>
    <p>If <code>n = 4</code>:</p>
    <pre><code>bunnyEars(4)
2 + bunnyEars(3)
2 + 2 + bunnyEars(2)
2 + 2 + 2 + bunnyEars(1)
2 + 2 + 2 + 2 + bunnyEars(0)

2 + 2 + 2 + 2 + 0 = 8</code></pre>
    <hr />
    <h2 id="g.">g.</h2>
    <pre><code>// arraySize === n
const search = (array, arraySize, target) =&gt; {
  if (arraySize &gt; 0) {
    if (array[arraySize - 1] === target) return true;
    else return search(array, arraySize - 1, target);
  }
  return false;
};</code></pre>
    <h3 id="linear-on-1">Linear — O(n)</h3>
    <p>
      The number of recursive calls grows with the input size of <code>n</code>.
      This function is linear since each recursive call decrements
      <code>n</code> by 1 until the base case of
      <code>arraySize &gt; 0</code> is reached or the <code>target</code> is
      found.
    </p>
    <hr />
    <h4 id="resources"><em>Resources</em></h4>
    <p>
      <em
        ><a href="https://wiki.python.org/moin/TimeComplexity"
          >Time-complexity of various Python operations</a
        ></em
      >
    </p>
  </body>
</html>
